﻿给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

输入 : words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出 : ["i", "love"]
解析 : "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

输入 : ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"] , k = 4
输出 : ["the", "is", "sunny", "day"]
解析 : "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

注意：
	1 <= words.length <= 500
	1 <= words[i] <= 10
	words[i] 由小写英文字母组成。
	k 的取值范围是[1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

class Solution {
    typedef pair<string, int> PSI;
    struct cmp {
        bool operator()(const PSI& a, const PSI& b) {
            if (a.second == b.second) // 频次相同，字典序按照⼤根堆的⽅式排列

            {
                return a.first < b.first;
            }
            return a.second > b.second;
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 1.统计⼀下每⼀个单词的频次

        unordered_map<string, int> hash;
        for (auto& s : words)
            hash[s]++;
        // 2.创建⼀个⼤⼩为k的堆

        priority_queue<PSI, vector<PSI>, cmp> heap;
        // 3. TopK的主逻辑

        for (auto& psi : hash) {
            heap.push(psi);
            if (heap.size() > k)
                heap.pop();
        }
        // 4.提取结果

        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};